#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "arvore_sa.h"

/* cria uma arvore vazia */
ArvoreSA *(cria_arvore_sa())
{
        ArvoreSA *raiz;

        raiz = NULL;

        return raiz;
}

/* consulta o caminho na arvore para chegar ao produto, imprime a frequencia e as
cidades que compram e as que vendem o produto */
void consulta_arvore_sa(ArvoreSA *raiz,char *produto)
{
        ArvoreSA *aux;
        char caminho[64] = "";
        int comp;

        aux = raiz;
	
	AchaRaiz(&raiz);

        /* caso o produto esteja na raiz da arvore */
        if (strcmp(produto,raiz->produto) == 0)
        {
                printf("R\n");
                printf("%d\n",raiz->frequencia);
                ImprimeCidades(raiz->compra);
                ImprimeCidades(raiz->vende);
                return;
        }

        /* caso nao esteja, vai descendo na arvore ate encontrar o produto ou a 
        posicao onde o produto deveria estar */
        while (aux != NULL)
        {
                comp = strcmp(produto,aux->produto);
                
                if (comp == 1)
                {
                        aux = aux->dir;
                        strcat(caminho,"D");
                }
                if (comp == -1)
                {
                        aux = aux->esq;
                        strcat(caminho,"E");
                }
                if (comp == 0 || aux == NULL)
                {
                        printf("%s\n",caminho);
                        if (aux != NULL)
                        {
                                printf("%d\n",aux->frequencia);
                                ImprimeCidades(aux->compra);
                                ImprimeCidades(aux->vende);
                        }
                        else
                                printf("0\n");
                        break;
                }
        }

        return;
}

/* busca o produto na arvore, retorna o proprio no caso o produto ja exista ou
o pai do no caso nao o produto nao esteja na arvore */
ArvoreSA *(Busca(char *produto,ArvoreSA *no))
{
        int comp;
        ArvoreSA *p;

        if (no != NULL)
        {
                comp = strcmp(produto,no->produto);
                if (comp == 1)
                {
                        if (no->dir == NULL)
                                return no;
                        else
                                p = Busca(produto,no->dir);
                }
                if (comp == -1)
                {
                        if (no->esq == NULL)
                                return no;
                        else
                                p = Busca(produto,no->esq);
                }
                if (comp == 0)
                        p = no;
        }
        return p;
}

/* verifica se o produto ja existe na arvore para rotacionar ou insere o produto na posicao certa
na arvore caso nao exista ainda */
ArvoreSA *(insere_arvore_sa(ArvoreSA *raiz,char *compra,char *vende,char *produto))
{
        ArvoreSA *busca;
        int comp;

        if (raiz == NULL)
        {            
                InsereArvore(&raiz,produto,compra,vende,NULL);
        }
        else
        {
                busca = Busca(produto,raiz);
                comp = strcmp(produto,busca->produto);
                if (comp == 0)
                {
                        InsereCidade(&(busca->compra),compra);
                        InsereCidade(&(busca->vende),vende);
                        busca->frequencia += 1;
				    Rotaciona(&busca);
				    AchaRaiz(&raiz);
                }
                else
                {
                        if (comp == 1)
                                InsereArvore(&(busca->dir),produto,compra,vende,busca);
                        if (comp == -1)
                                InsereArvore(&(busca->esq),produto,compra,vende,busca);
                }
        }

        return raiz;
}

/* aloca a memoria do no e inicializa as informacoes */
void InsereArvore(ArvoreSA **raiz,char *produto,char *compra,char *vende,ArvoreSA *pai)
{
        ArvoreSA *novo;

        novo = (ArvoreSA*)malloc(sizeof(ArvoreSA));
        novo->frequencia = 1;
        strcpy(novo->produto, produto);
        InsereCidade(&(novo->compra),compra);
        InsereCidade(&(novo->vende),vende);
        novo->pai = pai;
        novo->esq = NULL;
        novo->dir = NULL;

        *raiz = novo;
}
/* FUNCAO DE TESTE */
void Imprime(ArvoreSA *p)
{
        if (p != NULL) 
        {
                Imprime (p->esq);
                printf("%s  ", p->produto);
                Imprime (p->dir);
        }
}

/* libera a memoria alocada pela arvore e pelas listas ligadas das cidades que 
compram e vendem os produtos */
void libera_arvore_sa(ArvoreSA **lixo)
{
        if (*lixo != NULL)
        {
                libera_arvore_sa(&((*lixo)->esq));
                libera_arvore_sa(&((*lixo)->dir));
                LiberaCidades((&(*lixo)->compra));
                LiberaCidades((&(*lixo)->vende));
                free(*lixo);
        }
}

void Rotaciona (ArvoreSA **busca)
{
     int i = 0;
     int het;
     ArvoreSA *pai;
     if ((*busca)->pai != NULL)
     {
	  if((*busca)->frequencia >= (*busca)->pai->frequencia)
	  {
	       if((*busca)->pai->pai == NULL) /* o pai eh a raiz */
	       {	
		    if((*busca)->pai->esq == *busca)
			 RotacionaDir(busca, (*busca)->pai);
	       
		    else RotacionaEsq(busca, (*busca)->pai);
	       
		    return;
	       }
	  
	       het = checaHetero(busca);
	  
	       if(!het) /* nao eh heterogeneo */
	       {
		    if((*busca)->pai->frequencia >= (*busca)->pai->pai->frequencia)
		    {
			 /* Rotaciona busca->pai em torno de busca->pai->pai */
			 if((*busca)->pai->pai->esq == (*busca)->pai)
			 {
			      pai = (*busca)->pai;
			      RotacionaDir(&pai, (*busca)->pai->pai);
			 }
		    
			 else
			 {
			      pai = (*busca)->pai;
			      RotacionaEsq(&pai, (*busca)->pai->pai);
			 }
		    
			 if ((*busca)->pai->pai == NULL) return;
		    }	
	       }
	  
	       /* sendo heterogeneo */
	       if (het)
	       {
		    while(i<2)
		    {
			 if((*busca)->pai->esq == *busca)
			      RotacionaHetDir(busca, (*busca)->pai);
		    
			 else RotacionaHetEsq(busca, (*busca)->pai);
		    
			 i++;
		    }
		    
	       /* depois que rotacionou o heterogeneo, nao pode atualizar o busca, continua ele mesmo ateh a raiz */
	       }
     
	       else /* nao sendo nenhum dos casos, deve-se rotacionar o elemento em volta de seu pai */
	       {
		    if((*busca)->pai->esq == *busca)
			 RotacionaDir(busca, (*busca)->pai);
		    
		    else RotacionaEsq(busca, (*busca)->pai);  
	       }
	  
	       /* depois que rotacionou o heterogeneo, nao pode atualizar o busca, continua ele mesmo ateh a raiz */
	       if (!het)
		    *busca = (*busca)->pai;
	  
	       Rotaciona(busca);
	  }
     }
}

int checaHetero(ArvoreSA** no)
{
     if(((*no)->pai->pai->esq == (*no)->pai && (*no)->pai->dir == *no) || ((*no)->pai->pai->dir == (*no)->pai && (*no)->pai->esq == *no ))
	  return 1;
     
     else return 0;
}

void RotacionaEsq (ArvoreSA **no, ArvoreSA *pai)
{
	pai->dir = (*no)->esq;
	
	if ((*no)->esq != NULL)
		(*no)->esq->pai = pai;
	
	(*no)->esq = pai;
	
	if (pai->pai != NULL)
		pai->pai->dir = *no;
	
	/* atualizando ponteiros dos pais */
	(*no)->pai = pai->pai;
	
	pai->pai = *no;
}

void RotacionaDir (ArvoreSA **no, ArvoreSA *pai)
{
     pai->esq = (*no)->dir;
     
     if ((*no)->dir != NULL)
	(*no)->dir->pai = pai;
	
     (*no)->dir = pai;
     
     if (pai->pai != NULL)
	pai->pai->esq = *no;
	
	(*no)->pai = pai->pai;
	
	pai->pai = *no;
}

void RotacionaHetEsq(ArvoreSA **no, ArvoreSA *pai)
{
     pai->dir = (*no)->esq;
     
     if((*no)->esq != NULL)
	  (*no)->esq->pai = pai;
     
     (*no)->pai = pai->pai;
     pai->pai->esq = *no;
     
     pai->pai = *no;
     (*no)->esq = pai;
     
}

void RotacionaHetDir(ArvoreSA **no, ArvoreSA *pai)
{
     pai->esq = (*no)->dir;
     
     if((*no)->dir != NULL)
	  (*no)->dir->pai = pai;
     
     (*no)->pai = pai->pai;
     pai->pai->dir = *no;
     
     pai->pai = *no;
     (*no)->dir = pai;
     
}


void AchaRaiz(ArvoreSA **no)
{
	while ((*no)->pai != NULL)
		(*no) = (*no)->pai;

	return;
}
